package 简单.并查集;

/**
 * 有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。
 * 图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和
 * 顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
 * 请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
 * 给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination
 * 存在 有效路径 ，则返回 true，否则返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-if-path-exists-in-graph
 */
public class 寻找图中是否存在路径_1971 {

    public static void main(String[] args) {

    }

    /**
     * 并查集
     */
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        DSU dsu = new DSU(n);
        for (int[] edge : edges) {
            dsu.union(edge[0], edge[1]);
        }

        return dsu.connected(source, destination);
    }

    static class DSU {

        private int[] pre;

        public DSU(int n) {
            pre = new int[n];
            for (int i = 0; i < pre.length; i++) {
                pre[i] = i;
            }
        }

        public int find(int x) {
            if (pre[x] == x) return x;

            return pre[x] = find(pre[x]);
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;

            pre[x] = y;
        }

        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }

}
